

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.ArrayList;


public class Ejercicio3SinPodas {
	
	public String fileNameIn = "/home/chudi/workspace/algo32009vamosaverquesale/algo3/TP1/src/Tp1Ej3_saco13.in";
	public String fileNameOut = "/home/chudi/workspace/algo32009vamosaverquesale/algo3/TP1/src/Tp1Ej3_saco13_sinPodas.out";
	
	public static final String horizontal = "horizontal";
	public static final String vertical = "vertical";
	private static int cantSolPorComponente = 0;
	
	public static int contOperaciones = 0;
	
	public enum TipoPieza {horizontal, vertical};
	
	private static Integer cantSol = 1; 
	private static Integer cantLibres = 0;
	private static Integer[][] tablero;
	
	private static int casillerosSinPintarFill;
	
	private static ArrayList<ComponenteConex> listComConex;
	
	private static boolean tengoUnaComponenteMala = false;
	

	/**
	 * @param args
	 */
	
	public void leeteElArchivo() throws Exception {

		BufferedWriter bw = null;
		bw = new BufferedWriter(new FileWriter(new File(fileNameOut)));
		
		BufferedReader br = null;
		br = new BufferedReader(new FileReader(new File(fileNameIn)));
		String linea = br.readLine();
		Integer cantidad_filas = Integer.parseInt(linea.trim());
		while (cantidad_filas != -1) {
			contOperaciones = 0;
			long init = System.nanoTime();
			tablero = new Integer [cantidad_filas][cantidad_filas];
			cantLibres = 0;
			cantSol = 0;
			String lineaString = br.readLine();
			
			for(int i = 0 ; i < cantidad_filas; i++) {
				for(int j = 0 ; j < cantidad_filas ; j++) {
					char caracter = lineaString.charAt(j);
					if(caracter == '_') {
						tablero[i][j] = -1;
					} else {
						tablero[i][j] = 0;
						cantLibres++;
					}
					contOperaciones++;
				}
				lineaString = br.readLine();
				int pato = Integer.MAX_VALUE;
			}
			
			
			
// Busca componentes conexas del algoritmo		
//			listComConex = new ArrayList<ComponenteConex>();contOperaciones++;
//			Integer[] newXY = buscarProximaUbicacion(0, 0, 0, 0);contOperaciones++;
//			int colorReemplazo = 10;contOperaciones++;
//			casillerosSinPintarFill = cantLibres;contOperaciones++;
//			while(casillerosSinPintarFill > 0){
//				newXY = buscarProximaUbicacion(0, 0, 0, 0);contOperaciones++;
//				ComponenteConex compConexa = new ComponenteConex(colorReemplazo,newXY);contOperaciones++;				
//				floodFill(newXY[0], newXY[1], 0, colorReemplazo,compConexa);contOperaciones++;
//				if (checkearComponenteConexa(compConexa)){
//					break;contOperaciones++; 
//				}
//				
//				listComConex.add(compConexa);contOperaciones++;
//				colorReemplazo += 2;contOperaciones++;
//			}
			
			if(true){
//				Collections.sort(listComConex);contOperaciones++;
//				Iterator<ComponenteConex> it = listComConex.iterator();contOperaciones++;
//				while (it.hasNext() && !tengoUnaComponenteMala) {
//					ComponenteConex componente = (ComponenteConex) it.next();contOperaciones++;
//					ponerObligatorias(componente);contOperaciones++;
//					if(componente.cantidad == 0){
//						it.remove();contOperaciones++;
//					}
//				}
				
//				Iterator<ComponenteConex> it2 = listComConex.iterator();contOperaciones++;
//				while (it2.hasNext() && !tengoUnaComponenteMala) {
//					ComponenteConex componente = (ComponenteConex) it2.next();contOperaciones++;
//					
					Integer[] newXY = buscarProximaUbicacion(0, 0, 0, 0);contOperaciones++;
//					cantSolPorComponente = 0;contOperaciones++;
					if(newXY != null){
						tapar(newXY[0], newXY[1], TipoPieza.horizontal, 0, 0 );contOperaciones++;
						tapar(newXY[0], newXY[1], TipoPieza.vertical, 0, 0);contOperaciones++;
					}
					
					
//					tengoUnaComponenteMala = cantSolPorComponente == 0;contOperaciones++;
//					cantSol *= cantSolPorComponente;contOperaciones++;
//				}
				
			}

			
			if(tengoUnaComponenteMala){
//				System.out.println("Sali por mala: 0");contOperaciones++;
				System.out.println( cantidad_filas + (System.nanoTime() - init));
				bw.append("0");
			}else{
//				System.out.println("Cantidad de soluciones: " + cantSol.toString());contOperaciones++;
				System.out.println(cantidad_filas * cantidad_filas + " " + (System.nanoTime() - init));
				bw.append(cantSol.toString());
			}
			bw.newLine();
			tengoUnaComponenteMala = false;

			cantidad_filas = Integer.parseInt(lineaString);

//			listComConex.clear();contOperaciones++;
//			System.out.println("----------------------TERMINO------------------------------");contOperaciones++;
		}
		br.close();contOperaciones++;
		bw.close();contOperaciones++;
	}

	/**
	 * Checkea el tablero y pone todas las veces necesarias las piezas obligatorias por cada componente conexa
	 * @param componente
	 */
	private static void ponerObligatorias(ComponenteConex componente) {
		Integer[] newXY = componente.nodoInit;contOperaciones++;

//		System.out.println("Esta es la inicial del nodo: " + Arrays.toString(newXY));contOperaciones++;
//		System.out.println("Esta es mi color: " + componente.color);contOperaciones++;
		while( newXY != null && !tengoUnaComponenteMala){
			if(pongoObligatoria(newXY, componente.color, componente.color+1)){
				componente.cantidad -=2;contOperaciones++;
				cantLibres -=2;contOperaciones++;
				newXY = componente.nodoInit;contOperaciones++; // Vuelvo atras a la coordenada inicial, porque ya puse en este ciclo
			}
//			System.out.println("Esta es la prox del nodo: " + Arrays.toString(newXY));contOperaciones++;
			newXY = buscarProximaUbicacion(newXY[0], newXY[1] + 1, componente.color, componente.color+1);contOperaciones++;
		}
//		System.out.println("sali");contOperaciones++;
		
	}

	/***
	 * Pone una pieza obligatoria en el lugar XY, mira alrededor y si encuentra mas de una opcion, devuelve falso, sino pone la ficha
	 * @param newXY
	 * @param color1
	 * @param color2
	 * @return
	 */
	private static boolean pongoObligatoria(Integer[] newXY, int color1, int color2) {
		int contadorCasillerosLibresAlrededor = 0;contOperaciones++;
		Integer fila = newXY[0];contOperaciones++;
		Integer col = newXY[1];contOperaciones++;
		
		TipoPieza tipoPieza = null;contOperaciones++;
		Integer filaCand = null;contOperaciones++;
		Integer colCand = null;contOperaciones++;
		
		if(fila - 1 >= 0 && (tablero[fila-1][col].equals(color1) || tablero[fila-1][col].equals(color2)) ){
			contadorCasillerosLibresAlrededor++;contOperaciones++;
			filaCand = fila - 1  ;contOperaciones++;
			colCand = col;contOperaciones++;
			tipoPieza = TipoPieza.vertical;contOperaciones++;
		}
		
		if( fila+1 < tablero.length && (tablero[fila+1][col].equals(color1) || tablero[fila+1][col].equals(color2)) ){
			contadorCasillerosLibresAlrededor++;contOperaciones++;
			filaCand = fila;contOperaciones++; // Ajusto la filaCandidato, para poner la ficha
			colCand = col;contOperaciones++;
			tipoPieza = TipoPieza.vertical;contOperaciones++;
		}
		
		if( col - 1 >= 0 && (tablero[fila][col - 1].equals(color1) || tablero[fila][col - 1].equals(color2)) ){
			contadorCasillerosLibresAlrededor++;contOperaciones++;
			filaCand = fila;contOperaciones++;
			colCand = col - 1;contOperaciones++;
			tipoPieza = TipoPieza.horizontal;contOperaciones++;
		}
		
		if( col + 1 < tablero.length && (tablero[fila][col + 1].equals(color1) || tablero[fila][col + 1].equals(color2)) ){
			contadorCasillerosLibresAlrededor++;contOperaciones++;
			filaCand = fila;contOperaciones++;
			colCand = col;contOperaciones++; // Ajusto la colCandidato, para poner la ficha
			tipoPieza = TipoPieza.horizontal;contOperaciones++;
		}
		
		if(contadorCasillerosLibresAlrededor > 1){
			return false;
		}
		
		
		ponerPieza(filaCand, colCand, tipoPieza);contOperaciones++;
		
//		System.out.println("Estoy en: [" + fila + "," + col + "] puse la obligatoria: [" + filaCand + "," + colCand + "]");contOperaciones++;
		imprimirSol();contOperaciones++;
		tengoUnaComponenteMala = puedoPodar(filaCand, colCand, tipoPieza, color1, color2);contOperaciones++;
//		System.out.println("Tengo componente mala?" + tengoUnaComponenteMala);contOperaciones++;
		return true;
	}

	private static boolean checkearComponenteConexa(ComponenteConex compConexa) {
		if( (compConexa.blancos != compConexa.negros) || (compConexa.cantidad % 2 != 0)){
			tengoUnaComponenteMala = true;
			return tengoUnaComponenteMala;
		}
		tengoUnaComponenteMala = false;contOperaciones++;
		return tengoUnaComponenteMala;
	}

	private static void floodFill(Integer x, Integer y, int colorObj, int colorReemplazo, ComponenteConex compConexa) {
		if( x == tablero.length || y == tablero.length || x < 0 || y < 0){
			return;
		}
		if (tablero[x][y] != colorObj) {
			return;
		}
		
		if (tablero[x][y] == colorReemplazo) {
			return;
		}
		
		compConexa.cantidad += 1;contOperaciones++;
		casillerosSinPintarFill--;contOperaciones++;
		
		if(colorReemplazo % 2 == 0){//Blancos es par
			compConexa.blancos++;contOperaciones++;
			colorReemplazo++;contOperaciones++;
		} else {
			compConexa.negros++;contOperaciones++;
			colorReemplazo--;contOperaciones++;
		}
		tablero[x][y] = colorReemplazo;contOperaciones++;
		
		floodFill(x - 1, y, colorObj, colorReemplazo,compConexa);contOperaciones++;
		floodFill(x + 1, y, colorObj, colorReemplazo,compConexa);contOperaciones++;
		floodFill(x, y - 1, colorObj, colorReemplazo,compConexa);contOperaciones++;
		floodFill(x, y + 1, colorObj, colorReemplazo,compConexa);contOperaciones++;
	}

	public static void tapar(Integer fila, Integer col, TipoPieza tipoPieza, int color1, int color2) {
		if( !puedoPonerPieza(fila, col, tipoPieza, color1, color2 ) ) {
			contOperaciones++;
			return;
		}
		
		ponerPieza(fila, col, tipoPieza);contOperaciones++;
		cantLibres--;contOperaciones++;
		cantLibres--;contOperaciones++;
		boolean poda = false;contOperaciones++;
//		if(fila<tablero.length && col < tablero.length && puedoPodar(fila, col, tipoPieza, color1, color2)) {
//			poda = true;contOperaciones++;
//		}
		
		Integer[] newXY = buscarProximaUbicacion(fila, col, color1, color2);contOperaciones++;
		
		if(cantLibres.equals(0)) {
			cantSol++;contOperaciones++;
		} else if (poda){
			;contOperaciones++;
		}else{	
			tapar(newXY[0], newXY[1], TipoPieza.horizontal, color1, color2);contOperaciones++;
			tapar(newXY[0], newXY[1], TipoPieza.vertical, color1, color2);contOperaciones++;
		}
		
		sacarPieza(fila, col, tipoPieza, color1, color2);contOperaciones++;
		cantLibres++;contOperaciones++;
		cantLibres++;contOperaciones++;
	}

	private static boolean puedoPodar(Integer fila, Integer col, TipoPieza tipoPieza, int color1, int color2) {
		if(tipoPieza.equals(TipoPieza.horizontal)) {
			
			if(fila+1 < tablero.length && (tablero[fila+1][col].equals(color1) || tablero[fila+1][col].equals(color2)) ){
				if(!chequearDeAbajo(fila+1,col,color1,color2) ){
//					System.out.println("PODA HORIZONTAL 1");contOperaciones++;
					return true;
				}			
			}
			
			if(fila+1 < tablero.length && col+1 < tablero.length && (tablero[fila+1][col+1].equals(color1) || tablero[fila+1][col+1].equals(color2))){
				if(!chequearDeAbajo(fila+1,col+1,color1,color2)){
//					System.out.println("PODA HORIZONTAL 2");contOperaciones++;
					return true;
				}
			}
			
		}else {
			if(fila+1 < tablero.length && col-1 >= 0 && (tablero[fila+1][col-1].equals(color1) || tablero[fila+1][col-1].equals(color2))){
				if(!chequearDeAbajo(fila+1,col-1,color1,color2)){
//					System.out.println("PODA VERTICAL 1");contOperaciones++;
					return true;
				}			
			}
			
			if(fila+2 < tablero.length &&  (tablero[fila+2][col].equals(color1) || tablero[fila+2][col].equals(color2))){
				if(!chequearDeAbajo(fila+2,col,color1,color2)){
//					System.out.println("PODA VERTICAL 2");contOperaciones++;
					return true;
				}
			}
			
			if(fila+1 < tablero.length && col+1 < tablero.length  && (tablero[fila+1][col+1].equals(color1) || tablero[fila+1][col+1].equals(color2))){
				if(!chequearDeAbajo(fila+1,col+1,color1,color2) ){
//					System.out.println("Esto en fila: " + fila + "col: "+ col);contOperaciones++;
//					System.out.println("Color1: " + color1 + " color2: "+ color2);contOperaciones++;
//					System.out.println("PODA VERTICAL 3");contOperaciones++;
					return true;
				}			
			}
		}
	
		return false;
	}

	private static boolean chequearDeAbajo(int i, int j, int color1, int color2) {
		
		boolean chequeo = false;contOperaciones++;
	
		if(i+1<tablero.length && j < tablero.length && (tablero [i+1][j].equals(color1) || tablero [i+1][j].equals(color2)) ){
//			System.out.println("aca toy 1");contOperaciones++;
			chequeo |= true;contOperaciones++;
		}
		
		if(i<tablero.length && j+1 < tablero.length && (tablero [i][j+1].equals(color1) || tablero [i][j+1].equals(color2)) ){
//			System.out.println("aca toy 2");contOperaciones++;
			chequeo |= true;contOperaciones++;
		}
		
		if(i<tablero.length && j-1 >= 0 && ( tablero [i][j-1].equals(color1) || tablero [i][j-1].equals(color2))){
//			System.out.println("aca toy 3");contOperaciones++;
			chequeo |= true;contOperaciones++;
		}
		
		if(i-1 >= 0 && j < tablero.length && (tablero [i-1][j].equals(color1) || tablero [i-1][j].equals(color2))){
//			System.out.println("aca toy 4");contOperaciones++;
			chequeo |= true;contOperaciones++;
		}
		
		return chequeo;
	}

	private static void imprimirSol() {
//		String newLine = System.getProperty("line.separator");contOperaciones++;
//		StringBuffer sb = new StringBuffer();contOperaciones++;
//		for (int i = 0;contOperaciones++; i < tablero.length;contOperaciones++; i++) {
//			for (int j = 0;contOperaciones++; j < tablero.length;contOperaciones++; j++) {
//				if(tablero[i][j] == 1) {
//						sb.append("== ");contOperaciones++;
//				} else if(tablero[i][j] == 2) {
//					sb.append("|| ");contOperaciones++;
//			    } else if(tablero[i][j] == -1) {
//					sb.append(".. ");contOperaciones++;
//			    } else if(tablero[i][j] == 0) {
//					sb.append("VV ");
//			    } else {
//			    	sb.append(tablero[i][j] + " ");
//			    }
//			}
//			sb.append(newLine);
//		}
//		System.out.println(sb.toString());
//		System.out.println(newLine);
	}

	private static void sacarPieza(Integer filaAnterior, Integer colAnterior, TipoPieza tipoPieza, int color1, int color2) {
		if(tipoPieza.equals(TipoPieza.horizontal)) {
			contOperaciones++;contOperaciones++;contOperaciones++;
			tablero[filaAnterior][colAnterior] = color1;
			tablero[filaAnterior] [colAnterior +1] = color2;
		} else {
			contOperaciones++;contOperaciones++;contOperaciones++;
			tablero[filaAnterior][colAnterior] = color1;
			tablero[filaAnterior + 1] [colAnterior] = color2;
		}
	}

	private static Integer[] buscarProximaUbicacion(Integer fila, Integer col, int color1, int color2) {
		Integer[] res = new Integer[2];
		contOperaciones++;
		for (; fila < tablero.length; fila++) {
			for (; col < tablero.length; col++) {
				if(tablero[fila][col].equals( color1 ) || tablero[fila][col].equals( color2 )) {
					contOperaciones++;contOperaciones++;
					contOperaciones++;contOperaciones++;contOperaciones++;
					res[0] = fila;
					res[1] = col;
					return res;
				}
			}
			col = 0;
		}
//		res[0] = fila;
//		res[1] = col;

//		return res;
//		System.out.println("No encontre proxima ubicacion desde las coord: [" + fila +"," + col + "]" );
		return null;
	}

	private static void ponerPieza(Integer fila, Integer col, TipoPieza tipoPieza) {
		if(tipoPieza.equals(TipoPieza.horizontal)) {
			contOperaciones++;contOperaciones++;
			tablero[fila][col] = 1;
			tablero[fila] [col +1] = 1;
		} else {
			contOperaciones++;contOperaciones++;
			tablero[fila][col] = 2;
			tablero[fila + 1] [col] = 2;
		}
		
	}

	private static boolean puedoPonerPieza(Integer fila, Integer col, TipoPieza tipoPieza, int color1, int color2) {
		
		if(tipoPieza.equals(TipoPieza.horizontal)) {
			contOperaciones++;
			if(col.equals(tablero.length - 1)) {
				contOperaciones++;
				return false;
			} 
			
			if((tablero[fila][col].equals(color1)|| tablero[fila][col].equals(color2))&& (tablero[fila][col + 1].equals(color1)|| tablero[fila][col + 1].equals(color2))) {
				contOperaciones++;contOperaciones++;contOperaciones++;contOperaciones++;
				contOperaciones++;
				return true;
			} else {
				contOperaciones++;
				return false;
			}
			
		} else {
			if(fila.equals(tablero.length - 1)) {
				contOperaciones++;
				return false;
			} 
			
			if((tablero[fila][col].equals(color1)|| tablero[fila][col].equals(color2)) && (tablero[fila + 1][col].equals(color1)|| tablero[fila + 1][col].equals(color2))) {
				contOperaciones++;contOperaciones++;contOperaciones++;contOperaciones++;contOperaciones++;
				return true;
			} else {
				contOperaciones++;
				return false;
			}
		}
	}

	public static void main(String[] args) {
		if (args.length > 0){
//			fileNameIn = args[0];
		}
		
		try {
			Ejercicio3SinPodas test = new Ejercicio3SinPodas();
			if (args.length > 0){
				test.fileNameIn = args[0];
			}
			
			test.leeteElArchivo();
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

	}
	


}
